package com.datastructure.stackandqueue;

/**
 * @author: 临晖
 * @date: 2023/10/19
 * @description:
 */


import java.util.*;

/**
 * 栈与队列
 */
public class Solution01 {


    /**
     * 有效括号
     * <p>
     * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
     * 有效字符串需满足：
     * 左括号必须用相同类型的右括号闭合。
     * 左括号必须以正确的顺序闭合。
     * 每个右括号都有一个对应的相同类型的左括号。
     *
     * @param s
     * @return
     */
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        HashMap<Character, Character> map = new HashMap<>();
        map.put('(', ')');
        map.put('[', ']');
        map.put('{', '}');
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (stack.empty() && (ch == ')' || ch == ']' || ch == '}')) {
                return false;
            }


            if (ch == '(' || ch == '[' || ch == '{') {
                stack.push(map.get(ch));
            } else {
                Character pop = stack.pop();

                if (pop != ch) {
                    return false;
                }
            }

        }


        //for (int i = 0; i < s.length(); i++) {
        //    char ch = s.charAt(i);
        //    if (stack.empty() && (ch == ')' || ch == ']' || ch == '}')) {
        //        return false;
        //    }
        //
        //    if (ch == '[') {
        //        stack.push(']');
        //    } else if (ch == '{') {
        //        stack.push('}');
        //    } else if (ch == '(') {
        //        stack.push(')');
        //    } else {
        //        Character pop = stack.pop();
        //
        //        if (pop != ch) {
        //            return false;
        //        }
        //
        //    }
        //}
        return stack.empty();
    }


    /**
     * 删除字符串中的所有相邻重复项
     * <p>
     * 给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
     * 在 S 上反复执行重复项删除操作，直到无法继续删除。
     * 在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
     *
     * @param s
     * @return
     */
    public static String removeDuplicates(String s) {
        //思路一
        Stack<Character> stack = new Stack<>();


        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);

            if (!stack.empty() && stack.peek() == ch) {
                stack.pop();
                continue;
            }

            stack.push(ch);

        }
        String str = Arrays.toString(stack.toArray());
        s = "";
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) >= 'a' && str.charAt(i) <= 'z') {
                s += str.charAt(i);
            }
        }
        return s;

        //思路二
        //char[] ans = s.toCharArray();
        //int slow = -1;
        //int fast = 0;
        //
        //for (; fast < ans.length; fast++) {
        //    if (slow == -1 || ans[slow] != ans[fast]) {
        //        ans[++slow] = ans[fast];
        //    } else {
        //        --slow;
        //    }
        //}


        //return new String(Arrays.copyOf(ans, slow + 1));
    }


    /**
     * 给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
     * 请你计算该表达式。返回一个表示表达式值的整数。
     * <p>
     * 有效的算符为 '+'、'-'、'*' 和 '/' 。
     * 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
     * 两个整数之间的除法总是 向零截断 。
     * 表达式中不含除零运算。
     * 输入是一个根据逆波兰表示法表示的算术表达式。
     * 答案及所有中间计算结果可以用 32 位 整数表示。
     *
     * @param tokens
     * @return
     */
    public int evalRPN(String[] tokens) {
        Stack<String> stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            String ch = tokens[i];
            if ("+".equals(ch) || "-".equals(ch) || "*".equals(ch) || "/".equals(ch)) {
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                stack.push(getRes(num2, num1, ch));
            } else {
                stack.push(ch);
            }
        }

        return Integer.parseInt(stack.peek());
    }

    public String getRes(int num1, int num2, String ch) {
        int res = 0;
        switch (ch) {
            case "+":
                res = num1 + num2;
                break;
            case "-":
                res = num1 - num2;
                break;
            case "*":
                res = num1 * num2;
                break;
            case "/":
                res = num1 / num2;
                break;
        }
        return res + "";
    }


    /**
     * 239. 滑动窗口最大值
     * <p>
     * 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
     * 返回 滑动窗口中的最大值 。
     *
     * @param nums
     * @param k
     * @return
     */
    public static int[] maxSlidingWindow(int[] nums, int k) {
        //思路一，超时
        //Stack<Integer> stack = new Stack<>();
        //int[] newNums = new int[nums.length - k + 1];
        //int count = 0;
        //int skip = -1;
        //for (int i = 0; i < nums.length; i++) {
        //    skip++;
        //    if (skip != k) {
        //        if (stack.empty()) {
        //            stack.push(nums[i]);
        //        } else {
        //            int num = stack.pop();
        //            int max = num > nums[i] ? num : nums[i];
        //            stack.push(max);
        //        }
        //    } else {
        //        newNums[count++] = stack.pop();
        //        i -= k;
        //        skip = -1;
        //    }
        //}
        //newNums[count] = stack.pop();
        //return newNums;


        //思路二
        MyQu qu = new MyQu();
        int[] res = new int[nums.length - k + 1];
        int count = 0;

        for (int i = 0;i < k; i++) {
            qu.push(nums[i]);
        }
        res[count++] = qu.getMaxNum();



        for (int i = k; i < nums.length; i++) {
            qu.pop(nums[i - k]);
            qu.push(nums[i]);
            res[count++] = qu.getMaxNum();
        }

        return res;
    }


    /**
     * 前 K 个高频元素
     *
     * 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
     * @param nums
     * @param k
     * @return
     */
    public int[] topKFrequent(int[] nums, int k) {

        HashMap<Integer, Integer> map = new HashMap<>();
        //遍历数组中的数据，将数据中的数据存入map中   key：数字       value：数字出现频率
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        //基于小顶堆
        PriorityQueue<int[]> queue = new PriorityQueue<>((o1, o2) -> {
            return o1[1] - o2[1];
        });

        //遍历循环map，将map中的数据添加到优先队列中，并维持k个元素
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (queue.size() < k) {
                queue.add(new int[]{entry.getKey(), entry.getValue()});
            } else {
                if (entry.getValue() > queue.peek()[1]) {
                    queue.poll();
                    queue.add(new int[]{entry.getKey(), entry.getValue()});
                }
            }
        }

        //定义数组
        int[] res = new int[k];
        //将优先队列中的值依次弹出
        for (int i = 0; i < k; i++) {
            res[i] = queue.poll()[0];
        }
        return res;
    }



    public static void main(String[] args) {
        maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3);


    }

}

class MyQu {

    Deque<Integer> deque = new LinkedList<>();


    //如果出口值等于val，则弹出，否则不弹
    public void pop(int val) {
        if (!deque.isEmpty() && val == deque.peek()) {
            deque.removeFirst();        //移除出口元素
        }
    }


    //入队列，如果该值比前面的值都大，那么将前面得数据都弹出去(切记：这里不是直接和 出口元素/最大的元素 去比较，这里说的是，当a进入队列的时候，要
    //      把a前面所有比a小的元素都弹出去，即要从最小的开始比较，而不是一上来就和最大元素去比较，所以这里的比较规则是，从入口元素开始开始逐一
    //      比较
    //如果没有前面的值大，则正常入队列就行
    public void push(int val) {

        while (!deque.isEmpty() && val > deque.getLast()) {
            deque.removeLast();         //注意，从后面开始比较，从入口元素开始比较，比较到出口元素，所以这里是循环，
        }

        deque.add(val);         //从出口端添加
    }


    //队列中的最大值，即出口的
    public int getMaxNum() {
        return deque.getFirst();        //返回出口元素
    }

}
